package com.jack.leetcode.eachProblem07;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class 计算右侧小于当前元素的个数 {

    public static void main(String[] args) {
        int[] a = {5, 2, 6, 1};
        countSmaller(a).forEach(r -> {
            System.out.print(r + ",");
        });
    }

    private static int[] tmp;
    private static int[] result;
    private static int[] sort;

    public static List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return new ArrayList<>();
        }
        tmp = new int[n];
        result = new int[n];
        sort = new int[n];
        for (int i = 0; i < n; i++) {
            sort[i] = i;
        }
        mergeSort(nums, 0, n - 1);
        return Arrays.stream(result).boxed().collect(Collectors.toList());
    }

    private static void mergeSort(int[] nums, int l, int r) {
        if (l == r) {
            return;
        }
        int mid = (l + r) / 2;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        if (nums[sort[mid]] > nums[sort[mid + 1]]) {
            mergeTwoPart(nums, l, mid, r);
        }
    }

    private static void mergeTwoPart(int[] nums, int l, int mid, int r) {
        for (int i = l; i <= r; i++) {
            tmp[i] = sort[i];
        }
        int i = l;
        int j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                sort[k] = tmp[j++];
            } else if (j > r) {
                sort[k] = tmp[i++];
                result[sort[k]] += (r - mid);
            } else if (nums[tmp[i]] > nums[tmp[j]]) {
                sort[k] = tmp[j++];
            } else {
                sort[k] = tmp[i++];
                result[sort[k]] += (j - mid - 1);
            }
        }
    }
}
